package _剑指offer.二叉树;

import util.TreeNode;
import org.junit.Test;


/**
 * 输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
 * 
 * 方法一 从顶至底 + 深度比较 ：从顶至底 这个判断 当前子树的 左右子树高度差
 * 方法二 从底至顶 + 剪枝    ：
 */
public class _55_2_平衡二叉树 {
    @Test
    public void main() {
        Integer[] input = {1,2,3,4,5,6,7,6,7,8,null,8,9,null,null,null,null,9,10,11,12,13,null};
        TreeNode root = TreeNode.getTreeFromArray(input);
        System.out.println("isBalanced(root) = " + isBalanced(root));
    }
    
    public boolean isBalanced(TreeNode root) {
        if (height(root) <= 1) return true;
        if (Math.abs(height(root.left)-height(root.right))<=1) return true;
        return isBalanced(root.left) && isBalanced(root.right);
    }
    private int height(TreeNode root) {
        if (root == null) return 0;
        return Math.max(height(root.left), height(root.right)) + 1;
    }
    
    @Test
    public void main2() {
        Integer[] input = new Integer[]{3,9,20,null,null,15,7};
        TreeNode root = TreeNode.getTreeFromArray(input);
        System.out.println("isBalanced2(root) = " + isBalanced2(root));
    }
    
    public boolean isBalanced2(TreeNode root) {
        return false;
    }
}
